package com.binarysearch;

import java.util.*;

public class Solution1146 {
    public static void main(String[] args) {
        guessNumber(10);
    }
    public static int guessNumber(int n) {
        int i = 1;
        int j = n;
        while (i <= j) {
            int mid = (i + j) >> 1;
            int num = guess(mid);
            if (num == 0) {
                return mid;
            } else if (num == -1) i = mid + 1;
            else j = mid - 1;
        }
        return i;
    }
    static int guess(int num) {
        if (num == 6) {
            return 0;
        } else if (num < 6) {
            return -1;
        }
        return 1;
    }
}

class SnapshotArray {
    Map<Integer, List<Node>> map;
    int size;

    public SnapshotArray(int length) {
        map = new HashMap<>();
        size = 0;
        for (int i = 0; i < length; i++) {
            List<Node> list = new ArrayList<>();
            list.add(new Node(size, 0));
            map.put(i, list);
        }
    }

    public void set(int index, int val) {
        List<Node> list = map.get(index);
        list.add(new Node(size, val));
        map.put(index, list);
    }

    public int snap() {
        return size++;
    }

    public int get(int index, int snap_id) {
        List<Node> list = map.get(index);
        int n = list.size(), i = 0, j = n - 1;
        while (i < j) {
            int mid = (i + j + 1) >>> 1;
            if (list.get(mid).s <= snap_id) {
                i = mid;
            } else {
                j = mid - 1;
            }
        }
        return list.get(i).v;
    }
}

class Node {
    int s, v;

    public Node(int s, int v) {
        this.s = s;
        this.v = v;
    }
}